package solution._0030._0039;

import java.util.*;

/**
 * Created by chen_snow
 * Date: 2021/5/26 21:18
 * Description:
 */
public class Solution {

    public static void main(String[] args) {
        combinationSum(new int[]{2,3,5}, 8);
    }

    public static List<List<Integer>> result = new ArrayList<>();

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {

        Arrays.sort(candidates);

        combination(candidates, 0, target, new ArrayDeque<Integer>(), result);
        return result;
    }

    public static void combination(int[] candidates, int start, int left, Deque<Integer> data, List<List<Integer>> result) {
        if (left < 0) {
            return;
        } else if (left == 0) {
            List<Integer> tmp = new ArrayList<>(data);
            result.add(tmp);
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            data.addLast(candidates[i]);
            combination(candidates, i, left - candidates[i], data, result);
            data.removeLast();
        }
    }
}
